#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
char p[10010];
char s[1000010];
int Next[10010];
void kmp_pre(char* p){
    memset(Next,0,sizeof(Next));
    int i=0;
    int j=-1;
    Next[0]=-1;
    int l=strlen(p);
    while(i<l-1){
        if(j==-1 || p[i]==p[j]){
            i++;
            j++;
            Next[i]=j;
        }
        else{
            j=Next[j];
        }
    }
}
int kmp_cnt(char *s,char* p){
    kmp_pre(p);
    int sl=strlen(s);
    int pl=strlen(p);
    int i=0;
    int j=0;
    int cnt=0;
    while(i<sl && j<pl){
        if(j==-1 || s[i]==p[j]){
            i++;
            j++;
        }
        else{
            j=Next[j];
        }
        if(j==pl){
            cnt++;
            i--;
            j--;
            j=Next[j];
        }
    }
    return cnt;
}
int main(void){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%s",p);
        scanf("%s",s);
        int ans=kmp_cnt(s,p);
        printf("%d\n",ans);
    }
    return 0;
}
